
#include <bits/stdc++.h>

#define DataType int
#define MAXSIZE 100
using namespace std;

typedef struct
{
    int row, col;
    DataType value;
}Triple;

typedef struct
{
    Triple data[MAXSIZE + 1] = {{0,0,0}};   // 一维数组
    int rows, cols, nums;       //矩阵的行数，列数和非零元素个数
}TripleMatrix;

void FastTransposeTriMatrix (TripleMatrix *A, TripleMatrix *B)
{
    int col, t, p;
    int num[MAXSIZE] = {0}, cpot[MAXSIZE] = {0};
    cpot[1] = 1;
    if (B->nums)
    {
        for (t = 1; t <= A->nums; t++)
            num[A->data[t].col] ++;         //求M中每一列含非零元个数

        for (col = 2; col <= A->cols; col++)
            cpot[col] = cpot[col-1] + num[col-1];   //求M中每一列的第一个非零元在B.data中的序号（位置）


        for (p = 1; p <= A->nums; p++)
        {
            col = A->data[p].col;   //p为M中的行号, q为转置后在N中的行号
            int q = cpot[col];

            B->data[q].row = A->data[p].col;
            B->data[q].col = A->data[p].row;
            B->data[q].value = A->data[p].value;
            cpot[col]++;
        }
    }
}

/*
一个测试用例例子:

7 20 20
1 5 6
2 4 9
1 1 3
1 8 9
10 10 11
20 19 29
13 17 37

*/

int main()
{
    cout << "Please enter a ternary matrix, "
            "the first line is the number of elements n, rows, cols " << endl <<
            "and then the n-line is the row, column, value of an element: " << endl;
    int n, rows, cols;
    cin >> n >> rows >> cols;

    TripleMatrix a = {{}, rows+1, cols+1, n};
    TripleMatrix b = {{}, cols+1, rows+1, n};
    for(int i=1; i<=n; i++)  // data[0]空置
    {
        int temR, temC, temValue;
        cin >> temR >> temC >> temValue;
        a.data[i] = {temR, temC, temValue};
    }
    FastTransposeTriMatrix(&a, &b);

    cout << "Finished!" << endl;
    for(int i=1; i<=n; i++)
    {
        cout << b.data[i].row << " " << b.data[i].col << " " << b.data[i].value << endl;
    }

    return 0;
}
